package leetcode.newcoder;

import java.util.*;

/**
 * Created by tiang on 2018/7/25.
 * 题目描述
        给定一个 n 行 m 列的地牢，其中 '.' 表示可以通行的位置，'X' 表示不可通行的障碍，牛牛从 (x0 , y0 ) 位置出发，
     遍历这个地牢，和一般的游戏所不同的是，他每一步只能按照一些指定的步长遍历地牢，要求每一步都不可以超过地牢的边界，
     也不能到达障碍上。地牢的出口可能在任意某个可以通行的位置上。牛牛想知道最坏情况下，他需要多少步才可以离开这个地牢。
 输入描述:
        每个输入包含 1 个测试用例。每个测试用例的第一行包含两个整数 n 和 m（1 <= n, m <= 50），
     表示地牢的长和宽。接下来的 n 行，每行 m 个字符，描述地牢，地牢将至少包含两个 '.'。接下来的一行，
     包含两个整数 x0, y0，表示牛牛的出发位置（0 <= x0 < n, 0 <= y0 < m，左上角的坐标为 （0, 0），出发位置一定是 '.'）。
     之后的一行包含一个整数 k（0 < k <= 50）表示牛牛合法的步长数，接下来的 k 行，
     每行两个整数 dx, dy 表示每次可选择移动的行和列步长（-50 <= dx, dy <= 50）
 输出描述:
        输出一行一个数字表示最坏情况下需要多少次移动可以离开地牢，如果永远无法离开，输出 -1。
    以下测试用例中，牛牛可以上下左右移动，在所有可通行的位置.上，地牢出口如果被设置在右下角，
    牛牛想离开需要移动的次数最多，为3次。
 示例1
 输入

     3 3
     ...
     ...
     ...
     0 1
     4
     1 0
     0 1
     -1 0
     0 -1
 输出

    3
 */
public class EscapeFromJail {
    /**
     * 题目本身倒是算不上有多难，方法就是广度优先遍历
     * 但是题目的理解就很蛋疼了。首先后面的k中走法说的意思是：当你位于坐标(x,y)的时候，你可以有以下k中走法
     * 其次，这个题目中是允许跳过障碍物的。比如有一种走法是(2, 0)，当前坐标是(0,0),(1, 0)位置有个障碍物，但是仍然可以跳过障碍物到达(2,0)位置
     * 最后，走法(2,0)你要是走的话，就必须走到(x+2, y)这个位置，而不能走到(x+1,y)这个位置，不能少走。
     * 搞清楚这几个问题之后，接下来就是正常代码了。
     * @param args
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int rowCount = scanner.nextInt(),
                colCount = scanner.nextInt();
        char[][] map = new char[rowCount][colCount];
        scanner.nextLine();
        for(int i=0;i<rowCount;i++){
            String line = scanner.nextLine();
            char[] arr = line.toCharArray();
            for(int j=0;j<colCount;j++){
                map[i][j] = arr[j];
            }
        }
        Position start = new Position(scanner.nextInt(), scanner.nextInt());
        int k = scanner.nextInt();
        List<Position> list = new ArrayList<>();
        for(int i=0;i<k;i++){
            list.add(new Position(scanner.nextInt(), scanner.nextInt()));
        }
        int result = escapeFromJail(map, start, list);
        System.out.println(result);
    }
    static class Position{
        int x,y;
        public Position(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    private static int escapeFromJail(char[][] map, Position start, List<Position> steps){
        // 记录区域是否到达过
        boolean[][] arrival = new boolean[map.length][map[0].length];
        // 出发点已经到达过
        arrival[start.x][start.y] = true;
        // 迷宫的行数
        int rowCount = map.length;
        // 迷宫的列数
        int colCount = map[0].length;
        // 存储当前到达的位置
        Queue<Position> nowArrival = new LinkedList<>();
        nowArrival.add(start);
        //步数
        int stepCount = 0;
        while(!isFinished(map, arrival)){
            if(nowArrival.isEmpty())
                break;
            // 记录下一步可以到达的位置
            Queue<Position> nextStepArrival = new LinkedList<>();
            while(!nowArrival.isEmpty()){
                // 从当前位置出发，能到达多少个位置
                Position now = nowArrival.poll();
                for(Position step : steps) {
                    // 采用这种走法的话能到达哪个位置
                    Position next = new Position(now.x+step.x, now.y+step.y);
                    // 当前位置如果没有越界的话
                    if(next.x >= 0 && next.x<rowCount &&
                            next.y>=0 && next.y<colCount){
                        // 是否已经到达过
                        if(arrival[next.x][next.y])
                            continue;
                        else{
                            // 是否是障碍物
                            if(map[next.x][next.y] != 'X') {
                                arrival[next.x][next.y] = true;
                                nextStepArrival.add(next);
                            }
                        }
                    }
                    /**
                     * 走法为（dx,dy)时，如果允许走(1~dx,1~dy)步的话，就可以采用以下代码
                     */
                    /*List<Position> list = new ArrayList<>();
                    int rowMove = step.x;
                    boolean down = true;
                    if (step.x < 0) {
                        rowMove = 0 - step.x;
                        down = false;
                    }
                    for (int i = 1; i <= rowMove; i++) {
                        Position pos = new Position(down ? now.x + i : now.x - i, now.y);
                        if (pos.x < 0 || pos.x >= rowCount)
                            break;
                        list.add(pos);
                    }
                    int colMove = step.y;
                    boolean right = true;
                    if (step.y < 0) {
                        colMove = 0 - step.y;
                        right = false;
                    }
                    list.add(now);
                    ArrayList<Position> newList = new ArrayList<>();
                    for (Position pos : list) {
                        if(pos != now)
                            newList.add(pos);
                        for (int i = 1; i <= colMove; i++) {
                            Position temp = new Position(pos.x, right ? pos.y + i : pos.y - i);
                            if (temp.y < 0 || temp.y >= colCount)
                                break;
                            newList.add(temp);
                        }
                    }

                    for (Position pos : newList) {
                        if (arrival[pos.x][pos.y])
                            continue;
                        else {
                            arrivalCount++;
                            arrival[pos.x][pos.y] = true;
                            if(map[pos.x][pos.y] != 'X') {
                                System.out.print("("+pos.x+", "+pos.y+")");
                                nextStepArrival.add(pos);
                            }
                        }
                    }
                    System.out.println();*/
                }
            }
            nowArrival = nextStepArrival;
            // 步数+1
            stepCount++;
        }
        if(isFinished(map, arrival))
            return stepCount;
        else
            return -1;
    }

    /**
     * 判断是否所有能到达的点都已经到达
     * @param map
     * @param arrival
     * @return
     */
    private static boolean isFinished(char[][] map, boolean[][] arrival){
        for(int i=0;i<map.length;i++){
            for(int j=0;j<map[0].length;j++){
                if(map[i][j] == '.' && !arrival[i][j])
                    return false;
            }
        }
        return true;
    }
}
